home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / BitString.h < prev    next >
C/C++ Source or Header  |  1994-05-22  |  20KB  |  762 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifndef _BitString_h
  20. #ifdef __GNUG__
  21. #pragma interface
  22. #endif
  23.  
  24. #define _BitString_h 1
  25.  
  26. #include <stream.h>
  27. #include <limits.h>
  28.  
  29. #include <bitprims.h>
  30. #define BITSTRBITS  _BS_BITS_PER_WORD
  31.  
  32. struct BitStrRep
  33. {
  34.   unsigned int    len;          // length in bits
  35.   unsigned short  sz;           // allocated slots
  36.   _BS_word        s[1];         // bits start here
  37. };
  38.  
  39. extern BitStrRep*  BStr_alloc(BitStrRep*, const _BS_word*, int, int,int);
  40. extern BitStrRep*  BStr_resize(BitStrRep*, int);
  41. extern BitStrRep*  BStr_copy(BitStrRep*, const BitStrRep*);
  42. extern BitStrRep*  cmpl(const BitStrRep*, BitStrRep*);
  43. extern BitStrRep*  and(const BitStrRep*, const BitStrRep*, BitStrRep*);
  44. extern BitStrRep*  or(const BitStrRep*, const BitStrRep*, BitStrRep*);
  45. extern BitStrRep*  xor(const BitStrRep*, const BitStrRep*, BitStrRep*);
  46. extern BitStrRep*  diff(const BitStrRep*, const BitStrRep*, BitStrRep*);
  47. extern BitStrRep*  cat(const BitStrRep*, const BitStrRep*, BitStrRep*);
  48. extern BitStrRep*  cat(const BitStrRep*, unsigned int, BitStrRep*);
  49. extern BitStrRep*  lshift(const BitStrRep*, int, BitStrRep*);
  50.  
  51.  
  52. class BitString;
  53. class BitPattern;
  54.  
  55. class BitStrBit
  56. {
  57. protected:
  58.   BitString&        src;
  59.   unsigned int      pos;
  60.  
  61.  public:
  62.                     BitStrBit(BitString& v, int p);
  63.                     BitStrBit(const BitStrBit& b);
  64.                    ~BitStrBit();
  65.                     operator unsigned int() const;
  66.   int               operator =  (unsigned int b);
  67. };
  68.  
  69. class BitSubString
  70. {
  71.   friend class      BitString;
  72.   friend class      BitPattern;
  73.  
  74. protected:
  75.  
  76.   BitString&        S;
  77.   unsigned int      pos;
  78.   unsigned int      len;
  79.  
  80.                     BitSubString(BitString& x, int p, int l);
  81.                     BitSubString(const BitSubString& x);
  82. public:
  83.                     ~BitSubString();
  84.  
  85.   BitSubString&     operator =  (const BitString&);
  86.   BitSubString&     operator =  (const BitSubString&);
  87.  
  88.   int               length() const;
  89.   int               empty() const;
  90.  
  91.   int               OK() const;
  92. };
  93.  
  94. class BitString
  95. {
  96.   friend class       BitSubString;
  97.   friend class       BitPattern;
  98. protected:
  99.   BitStrRep*         rep;
  100.  
  101.   int                search(int, int, const _BS_word*, int, int) const;
  102.   int                match(int, int, int, const _BS_word*,int,int) const;
  103.   BitSubString       _substr(int first, int l);
  104.  
  105. public:
  106.  
  107. // constructors
  108.                      BitString();
  109.                      BitString(const BitString&);
  110.                      BitString(const BitSubString& y);
  111.  
  112.                     ~BitString();
  113.  
  114.   BitString&         operator =  (unsigned int bit);
  115.   BitString&         operator =  (const BitString& y);
  116.   BitString&         operator =  (const BitSubString& y);
  117.  
  118. // equality & subset tests
  119.  
  120.   friend int         operator == (const BitString&, const BitString&);
  121.   friend int         operator != (const BitString&, const BitString&);
  122.   friend int         operator <  (const BitString&, const BitString&);
  123.   friend int         operator <= (const BitString&, const BitString&);
  124.   friend int         operator >  (const BitString&, const BitString&);
  125.   friend int         operator >= (const BitString&, const BitString&);
  126.  
  127. // procedural versions of operators
  128.  
  129.  
  130.   friend void        and(const BitString&, const BitString&, BitString&);
  131.   friend void        or(const BitString&, const BitString&, BitString&);
  132.   friend void        xor(const BitString&, const BitString&, BitString&);
  133.   friend void        diff(const BitString&, const BitString&, BitString&);
  134.   friend void        cat(const BitString&, const BitString&, BitString&);
  135.   friend void        cat(const BitString&, unsigned int, BitString&);
  136.   friend void        lshift(const BitString&, int, BitString&);
  137.   friend void        rshift(const BitString&, int, BitString&);
  138.  
  139.   friend void        complement(const BitString&, BitString&);
  140.  
  141.   friend int         lcompare(const BitString&, const BitString&); 
  142.  
  143. // assignment-based operators
  144. // (constuctive versions decalred inline below
  145.  
  146.   BitString&         operator |= (const BitString&);
  147.   BitString&         operator &= (const BitString&);
  148.   BitString&         operator -= (const BitString&);
  149.   BitString&         operator ^= (const BitString&);
  150.   BitString&         operator += (const BitString&);
  151.   BitString&         operator += (unsigned int b);
  152.   BitString&         operator <<=(int s);
  153.   BitString&         operator >>=(int s);
  154.  
  155.   void               complement();
  156.  
  157. // individual bit manipulation
  158.  
  159.   void               set(int pos);
  160.   void               set(int from, int to);
  161.   void               set();
  162.  
  163.   void               clear(int pos);
  164.   void               clear(int from, int to);
  165.   void               clear(); 
  166.  
  167.   void               invert(int pos);
  168.   void               invert(int from, int to);
  169.  
  170.   int                test(int pos) const;
  171.   int                test(int from, int to) const;
  172.  
  173.   void               assign(int p, unsigned int bit);
  174.  
  175. // indexing
  176.  
  177.   BitStrBit          operator [] (int pos);
  178.  
  179. // iterators
  180.  
  181.   int                first(unsigned int bit = 1) const;
  182.   int                last(unsigned int b = 1) const;
  183.  
  184.   int                next(int pos, unsigned int b = 1) const;
  185.   int                prev(int pos, unsigned int b = 1) const;
  186.   int                previous(int pos, unsigned int b = 1) const
  187.     { return prev(pos, b); } /* Obsolete synonym */
  188.  
  189. // searching & matching
  190.  
  191.   int                index(unsigned int bit, int startpos = 0) const ;      
  192.   int                index(const BitString&, int startpos = 0) const;
  193.   int                index(const BitSubString&, int startpos = 0) const;
  194.   int                index(const BitPattern&, int startpos = 0) const;
  195.  
  196.   int                contains(const BitString&) const;
  197.   int                contains(const BitSubString&) const;
  198.   int                contains(const BitPattern&) const;
  199.  
  200.   int                contains(const BitString&, int pos) const;
  201.   int                contains(const BitSubString&, int pos) const;
  202.   int                contains(const BitPattern&, int pos) const;
  203.  
  204.   int                matches(const BitString&, int pos = 0) const;
  205.   int                matches(const BitSubString&, int pos = 0) const;
  206.   int                matches(const BitPattern&, int pos = 0) const;
  207.  
  208. // BitSubString extraction
  209.  
  210.   BitSubString       at(int pos, int len);
  211.   BitSubString       at(const BitString&, int startpos = 0); 
  212.   BitSubString       at(const BitSubString&, int startpos = 0); 
  213.   BitSubString       at(const BitPattern&, int startpos = 0); 
  214.  
  215.   BitSubString       before(int pos);
  216.   BitSubString       before(const BitString&, int startpos = 0);
  217.   BitSubString       before(const BitSubString&, int startpos = 0);
  218.   BitSubString       before(const BitPattern&, int startpos = 0);
  219.  
  220.   BitSubString       after(int pos);
  221.   BitSubString       after(const BitString&, int startpos = 0);
  222.   BitSubString       after(const BitSubString&, int startpos = 0);
  223.   BitSubString       after(const BitPattern&, int startpos = 0);
  224.  
  225. // other friends & utilities
  226.  
  227.   friend BitString   common_prefix(const BitString&, const BitString&, 
  228.                                    int pos = 0);
  229.   friend BitString   common_suffix(const BitString&, const BitString&, 
  230.                                    int pos = -1);
  231.   friend BitString   reverse(const BitString&);
  232.  
  233.   void               right_trim(unsigned int bit);
  234.   void               left_trim(unsigned int bit);
  235.  
  236. // status
  237.  
  238.   int                empty() const ;
  239.   int                count(unsigned int bit = 1) const;
  240.   int                length() const;
  241.  
  242. // convertors & IO
  243.  
  244.   friend BitString   atoBitString(const char* s, char f='0', char t='1');
  245.   // BitStringtoa is deprecated; do not use in new programs!
  246.   friend const char* BitStringtoa(const BitString&, char f='0', char t='1');
  247.   void             printon(ostream&, char f='0', char t='1') const;
  248.  
  249.   friend BitString   shorttoBitString(unsigned short);
  250.   friend BitString   longtoBitString(unsigned long);
  251.  
  252.   friend ostream&    operator << (ostream& s, const BitString&);
  253.  
  254. // misc
  255.  
  256.   void      error(const char* msg) const;
  257.  
  258. // indirect friends
  259.  
  260.   friend BitPattern  atoBitPattern(const char* s,
  261.                                   char f='0',char t='1',char x='X');
  262.   friend const char* BitPatterntoa(const BitPattern& p, 
  263.                                   char f='0',char t='1',char x='X');
  264.   int                OK() const;
  265. };
  266.  
  267.  
  268. class BitPattern
  269. {
  270. public:
  271.   BitString          pattern;
  272.   BitString          mask;
  273.  
  274.                      BitPattern();
  275.                      BitPattern(const BitPattern&);
  276.                      BitPattern(const BitString& p, const BitString& m);
  277.  
  278.                     ~BitPattern();
  279.  
  280.   friend const char* BitPatterntoa(const BitPattern& p, 
  281.                                  char f/*='0'*/,char t/*='1'*/,char x/*='X'*/);
  282.   void             printon(ostream&, char f='0',char t='1',char x='X') const;
  283.   friend BitPattern atoBitPattern(const char* s, char f,char t, char x);
  284.   friend ostream&   operator << (ostream& s, const BitPattern&);
  285.  
  286.   int               search(const _BS_word*, int, int) const;
  287.   int               match(const _BS_word* xs, int, int, int) const;
  288.  
  289.   int               OK() const;
  290. };
  291.  
  292. BitString  operator & (const BitString& x, const BitString& y);
  293. BitString  operator | (const BitString& x, const BitString& y);
  294. BitString  operator ^ (const BitString& x, const BitString& y);
  295. BitString  operator << (const BitString& x, int y);
  296. BitString  operator >> (const BitString& x, int y);
  297. BitString  operator - (const BitString& x, const BitString& y);
  298. BitString  operator + (const BitString& x, const BitString& y);
  299. BitString  operator + (const BitString& x, unsigned int y);
  300. BitString  operator ~ (const BitString& x);
  301. int operator != (const BitString& x, const BitString& y);
  302. int operator>(const BitString& x, const BitString& y);
  303. int operator>=(const BitString& x, const BitString& y);
  304.  
  305. extern BitStrRep    _nilBitStrRep;
  306. extern BitString    _nil_BitString;
  307.  
  308. // primitive bit extraction
  309.  
  310. // These must be inlined regardless of optimization.
  311.  
  312. inline int BitStr_index(int l) { return (unsigned)(l) / BITSTRBITS; }
  313.  
  314. inline int BitStr_pos(int l) { return l & (BITSTRBITS - 1); }
  315.  
  316.  
  317. // constructors & assignment
  318.  
  319. inline BitString::BitString() :rep(&_nilBitStrRep) {}
  320.  
  321. inline BitString::BitString(const BitString& x) :rep(BStr_copy(0, x.rep)) {}
  322.  
  323. inline BitString::BitString(const BitSubString& y) 
  324.    :rep (BStr_alloc(0, y.S.rep->s, y.pos, y.pos+y.len, y.len)) {}
  325.  
  326. inline BitString::~BitString()
  327. { 
  328.   if (rep != &_nilBitStrRep) delete rep;
  329. }
  330.  
  331. inline BitString shorttoBitString(unsigned short w) 
  332. { 
  333.   BitString r;
  334.   _BS_word ww = w;
  335. #if _BS_BIGENDIAN
  336.   abort();
  337. #endif
  338.   r.rep = BStr_alloc(0, &ww, 0, 8 * sizeof(short), 8 * sizeof(short));
  339.   return r;
  340. }
  341.  
  342. inline BitString longtoBitString(unsigned long w) 
  343. { 
  344.   BitString r;
  345. #if 1
  346.   _BS_word u = w;
  347.   r.rep = BStr_alloc(0, &u, 0, BITSTRBITS, BITSTRBITS);
  348. #else
  349.   unsigned short u[2];
  350.   u[0] = w & ((unsigned short)(~(0)));
  351.   u[1] = w >> BITSTRBITS;
  352.   r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
  353. #endif
  354.   return r;
  355. }
  356.  
  357. inline BitString& BitString::operator =  (const BitString& y)
  358. { 
  359.   rep = BStr_copy(rep, y.rep);
  360.   return *this;
  361. }
  362.  
  363. inline BitString& BitString::operator = (unsigned int b)
  364. { 
  365.   _BS_word bit = b;
  366.   rep = BStr_alloc(rep, &bit, 0, 1, 1);
  367.   return *this;
  368. }
  369.  
  370. inline BitString&  BitString::operator=(const BitSubString&  y)
  371. {
  372.   rep = BStr_alloc(rep, y.S.rep->s, y.pos, y.pos+y.len, y.len);
  373.   return *this;
  374. }
  375.  
  376. inline BitSubString::BitSubString(const BitSubString& x) 
  377.     :S(x.S), pos(x.pos), len(x.len) {}
  378.  
  379. inline BitSubString::BitSubString(BitString& x, int p, int l)
  380.      : S(x), pos(p), len(l) {}
  381.  
  382. inline BitSubString::~BitSubString() {}
  383.  
  384. inline BitPattern::BitPattern(const BitString& p, const BitString& m)
  385.     :pattern(p), mask(m) {}
  386.  
  387. inline BitPattern::BitPattern(const BitPattern& b)
  388.     :pattern(b.pattern), mask(b.mask) {}
  389.  
  390. inline BitPattern::BitPattern() {}
  391. inline BitPattern::~BitPattern() {}
  392.  
  393.  
  394. // procedural versions of operators
  395.  
  396. inline void and(const BitString& x, const BitString& y, BitString& r)
  397. {
  398.   r.rep = and(x.rep, y.rep, r.rep);
  399. }
  400.  
  401. inline void or(const BitString& x, const BitString& y, BitString& r)
  402. {
  403.   r.rep = or(x.rep, y.rep, r.rep);
  404. }
  405.  
  406. inline void xor(const BitString& x, const BitString& y, BitString& r)
  407. {
  408.   r.rep = xor(x.rep, y.rep, r.rep);
  409. }
  410.  
  411. inline void diff(const BitString& x, const BitString& y, BitString& r)
  412. {
  413.   r.rep = diff(x.rep, y.rep, r.rep);
  414. }
  415.  
  416. inline void cat(const BitString& x, const BitString& y, BitString& r)
  417. {
  418.   r.rep = cat(x.rep, y.rep, r.rep);
  419. }
  420.  
  421. inline void cat(const BitString& x, unsigned int y, BitString& r)
  422. {
  423.   r.rep = cat(x.rep, y, r.rep);
  424. }
  425.  
  426. inline void rshift(const BitString& x, int y, BitString& r)
  427. {
  428.   r.rep = lshift(x.rep, -y, r.rep);
  429. }
  430.  
  431. inline void lshift(const BitString& x, int y, BitString& r)
  432. {
  433.   r.rep = lshift(x.rep, y, r.rep);
  434. }
  435.  
  436. inline void complement(const BitString& x, BitString& r)
  437. {
  438.   r.rep = cmpl(x.rep, r.rep);
  439. }
  440.  
  441. // operators
  442.  
  443.  
  444. inline BitString& BitString::operator &= (const BitString& y)
  445. {
  446.   and(*this, y, *this);
  447.   return *this;
  448. }
  449.  
  450.  
  451. inline BitString& BitString::operator |= (const BitString& y)
  452. {
  453.   or(*this, y, *this);
  454.   return *this;
  455. }
  456.  
  457. inline BitString& BitString::operator ^= (const BitString& y)
  458. {
  459.   xor(*this, y, *this);
  460.   return *this;
  461. }
  462.  
  463. inline BitString& BitString::operator <<= (int y)
  464. {
  465.   lshift(*this, y, *this);
  466.   return *this;
  467. }
  468.  
  469. inline BitString& BitString::operator >>= (int y)
  470. {
  471.   rshift(*this, y, *this);
  472.   return *this;
  473. }
  474.  
  475. inline BitString& BitString::operator -= (const BitString& y)
  476. {
  477.   diff(*this, y, *this);
  478.   return *this;
  479. }
  480.  
  481. inline BitString& BitString::operator += (const BitString& y)
  482. {
  483.   cat(*this, y, *this);
  484.   return *this;
  485. }
  486.  
  487. inline BitString& BitString::operator += (unsigned int y)
  488. {
  489.   cat(*this, y, *this);
  490.   return *this;
  491. }
  492.  
  493. inline void BitString::complement()
  494. {
  495.   ::complement(*this, *this);
  496. }
  497.  
  498. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  499.  
  500. inline BitString  operator & (const BitString& x, const BitString& y) return r
  501. {
  502.   and(x, y, r);
  503. }
  504.  
  505. inline BitString  operator | (const BitString& x, const BitString& y) return r
  506. {
  507.   or(x, y, r);
  508. }
  509.  
  510. inline BitString  operator ^ (const BitString& x, const BitString& y) return r
  511. {
  512.   xor(x, y, r);
  513. }
  514.  
  515. inline BitString  operator << (const BitString& x, int y) return r
  516. {
  517.   lshift(x, y, r);
  518. }
  519.  
  520. inline BitString  operator >> (const BitString& x, int y) return r
  521. {
  522.   rshift(x, y, r);
  523. }
  524.  
  525. inline BitString  operator - (const BitString& x, const BitString& y) return r
  526. {
  527.   diff(x, y, r);
  528. }
  529.  
  530. inline BitString  operator + (const BitString& x, const BitString& y) return r
  531. {
  532.   cat(x, y, r);
  533. }
  534.  
  535. inline BitString  operator + (const BitString& x, unsigned int y) return r
  536. {
  537.   cat(x, y, r);
  538. }
  539.  
  540. inline BitString  operator ~ (const BitString& x) return r
  541. {
  542.   complement(x, r);
  543. }
  544.  
  545. #else /* NO_NRV */
  546.  
  547. inline BitString  operator & (const BitString& x, const BitString& y) 
  548. {
  549.   BitString r; and(x, y, r); return r;
  550. }
  551.  
  552. inline BitString  operator | (const BitString& x, const BitString& y) 
  553. {
  554.   BitString r; or(x, y, r); return r;
  555. }
  556.  
  557. inline BitString  operator ^ (const BitString& x, const BitString& y) 
  558. {
  559.   BitString r; xor(x, y, r); return r;
  560. }
  561.  
  562. inline BitString  operator << (const BitString& x, int y) 
  563. {
  564.   BitString r; lshift(x, y, r); return r;
  565. }
  566.  
  567. inline BitString  operator >> (const BitString& x, int y) 
  568. {
  569.   BitString r; rshift(x, y, r); return r;
  570. }
  571.  
  572. inline BitString  operator - (const BitString& x, const BitString& y) 
  573. {
  574.   BitString r; diff(x, y, r); return r;
  575. }
  576.  
  577. inline BitString  operator + (const BitString& x, const BitString& y) 
  578. {
  579.   BitString r; cat(x, y, r); return r;
  580. }
  581.  
  582. inline BitString  operator + (const BitString& x, unsigned int y) 
  583. {
  584.   BitString r; cat(x, y, r); return r;
  585. }
  586.  
  587. inline BitString  operator ~ (const BitString& x) 
  588. {
  589.   BitString r; complement(x, r); return r;
  590. }
  591.  
  592. #endif
  593.  
  594. // status, matching
  595.  
  596. inline int BitString::length() const
  597. { 
  598.   return rep->len;
  599. }
  600.  
  601. inline int BitString::empty() const
  602. { 
  603.   return rep->len == 0;
  604. }
  605.  
  606. inline int BitString::index(const BitString& y, int startpos) const
  607. {   
  608.   return search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  609. }
  610.  
  611. inline int BitString::index(const BitSubString& y, int startpos) const
  612. {   
  613.   return search(startpos, rep->len, y.S.rep->s, y.pos, y.pos+y.len);
  614. }
  615.  
  616. inline int BitString::contains(const BitString& y) const
  617. {   
  618.   return search(0, rep->len, y.rep->s, 0, y.rep->len) >= 0;
  619. }
  620.  
  621. inline int BitString::contains(const BitSubString& y) const
  622. {   
  623.   return search(0, rep->len, y.S.rep->s, y.pos, y.pos+y.len) >= 0;
  624. }
  625.  
  626. inline int BitString::contains(const BitString& y, int p) const
  627. {
  628.   return match(p, rep->len, 0, y.rep->s, 0, y.rep->len);
  629. }
  630.  
  631. inline int BitString::matches(const BitString& y, int p) const
  632. {
  633.   return match(p, rep->len, 1, y.rep->s, 0, y.rep->len);
  634. }
  635.  
  636. inline int BitString::contains(const BitSubString& y, int p) const
  637. {
  638.   return match(p, rep->len, 0, y.S.rep->s, y.pos, y.pos+y.len);
  639. }
  640.  
  641. inline int BitString::matches(const BitSubString& y, int p) const
  642. {
  643.   return match(p, rep->len, 1, y.S.rep->s, y.pos, y.pos+y.len);
  644. }
  645.  
  646. inline int BitString::contains(const BitPattern& r) const
  647. {
  648.   return r.search(rep->s, 0, rep->len) >= 0;
  649. }
  650.  
  651. inline int BitString::contains(const BitPattern& r, int p) const
  652. {
  653.   return r.match(rep->s, p, rep->len, 0);
  654. }
  655.  
  656. inline int BitString::matches(const BitPattern& r, int p) const
  657. {
  658.   return r.match(rep->s, p, rep->len, 1);
  659. }
  660.  
  661. inline int BitString::index(const BitPattern& r, int startpos) const
  662. {
  663.   return r.search(rep->s, startpos, rep->len);
  664. }
  665.  
  666. inline  int BitSubString::length() const
  667. { 
  668.   return len;
  669. }
  670.  
  671. inline  int BitSubString::empty() const
  672. { 
  673.   return len == 0;
  674. }
  675.  
  676. inline int operator != (const BitString& x, const BitString& y)
  677. {
  678.   return !(x == y);
  679. }
  680.  
  681. inline int operator>(const BitString& x, const BitString& y)
  682. {
  683.   return y < x;
  684. }
  685.  
  686. inline int operator>=(const BitString& x, const BitString& y)
  687. {
  688.   return y <= x;
  689. }
  690.  
  691. inline int BitString::first(unsigned int b) const
  692. {
  693.   return next(-1, b);
  694. }
  695.  
  696. inline int BitString::last(unsigned int b) const
  697. {
  698.   return prev(rep->len, b);
  699. }
  700.  
  701. inline int BitString::index(unsigned int bit, int startpos) const
  702. {
  703.   if (startpos >= 0)
  704.     return next(startpos - 1, bit);
  705.   else
  706.     return prev(rep->len + startpos + 1, bit);
  707. }
  708.  
  709. inline void BitString::right_trim(unsigned int b) 
  710. {
  711.   int nb = (b == 0)? 1 : 0;
  712.   rep = BStr_resize(rep, prev(rep->len, nb) + 1);
  713. }
  714.  
  715. inline void BitString::left_trim(unsigned int b)
  716. {
  717.   int nb = (b == 0)? 1 : 0;
  718.   int p = next(-1, nb);
  719.   rep = BStr_alloc(rep, rep->s, p, rep->len, rep->len - p);
  720. }
  721.  
  722. inline int BitString::test(int i) const
  723. {
  724.   return ((unsigned)(i) >= rep->len)? 0 : 
  725.          ((rep->s[BitStr_index(i)] & (1 << (BitStr_pos(i)))) != 0);
  726. }
  727.  
  728.  
  729. // subscripting
  730.  
  731. inline BitStrBit::BitStrBit(const BitStrBit& b) :src(b.src), pos(b.pos) {}
  732.  
  733. inline BitStrBit::BitStrBit(BitString& v, int p) :src(v), pos(p) {}
  734.  
  735. inline BitStrBit::~BitStrBit() {}
  736.  
  737. inline BitStrBit::operator unsigned int() const
  738. {
  739.   return src.test(pos);
  740. }
  741.  
  742. inline int BitStrBit::operator = (unsigned int b)
  743. {
  744.   src.assign(pos, b); return b;
  745. }
  746.  
  747. inline BitStrBit BitString::operator [] (int i)
  748. {
  749.   if ((unsigned)(i) >= rep->len) error("illegal bit index");
  750.   return BitStrBit(*this, i);
  751. }
  752.  
  753. inline BitSubString BitString::_substr(int first, int l)
  754. {
  755.   if (first < 0 || l <= 0 || (unsigned)(first + l) > rep->len)
  756.     return BitSubString(_nil_BitString, 0, 0) ;
  757.   else 
  758.     return BitSubString(*this, first, l);
  759. }
  760.  
  761. #endif
  762.